#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
template < class Type>
inline void Swap(Type &a, Type &b)
{
	Type temp = a;
	a = b;
	b = temp;
}
int Random(int p, int r)
{
	srand((unsigned)time(NULL));
	return (p + rand()%(abs(r -p)));
}
	
template <class Type>
int Partition(Type a[], int p, int r)
{
	int i = p,j = r+1;
	Type x = a[p];
	
	while(true)
	{
		while(a[++i] < x);
		while(a[--j] > x);
		if( i >= j) break;
		Swap(a[i],a[j]);
	}
	a[p] = a[j];
	a[j] = x;
	return j;
}
template <class Type>
int RandomizedPartition(Type a[], int p, int r)
{
	int i = Random(p , r);
	Swap(a[i],a[p]);
	return Partition(a,p,r);
}
template < class Type>
Type RandomizedSelect(Type a[], int p, int r, int k)
{
	if( p == r) return a[p];
	int i = RandomizedPartition(a,p,r);
	int j = i - p + 1;
	if( k <= j) return RandomizedSelect(a,p,i-1,k);
	return RandomizedSelect(a,i+1,r,k-j);
}
template < class Type>
Type Master(Type a[],int n)
{
Type median = RandomizedSelect(a,0,n-1,n/2);
	int  cnt = 0;
for( int i = 0; i <= n-1; i++)
	if(a[i] == median)
		cnt ++;
if(cnt > n/2)
{
	std::cout << " The master element: " << median << std::endl;
	return median;
}
else
{
	std::cout << " No master element" << std::endl;
	return (Type)0;
}

}		
	int main()
	{
		int a[20] = {2,2,3,2,5,2,6,2,2,4,3,3,3,3,3,3,3,3,3,3};
		Master(a,20);
		return 0;
	}